﻿// 1001train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

/*
输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知）
和初始计数值m
从数列首位位置开始计数，计数到m后，将数列该位置数值替换计数值m，
并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止
如果计数到达数列尾段，则返回数列首位置继续计数
请编程实现上述计数过程，同时输出数值出列的顺序
比如：输入的随机数列为：3,1,2,4，初始计数值m=7，从数列首位位置开始计数（数值3所在位置）
第一轮计数出列数字为2，计数值更新m=2，出列后数列为3,1,4，从数值4所在位置从新开始计数
第二轮计数出列数字为3，计数值更新m=3，出列后数列为1,4，从数值1所在位置开始计数
第三轮计数出列数字为1，计数值更新m=1，出列后数列为4，从数值4所在位置开始计数
最后一轮计数出列数字为4，计数过程完成。输出数值出列顺序为：2,3,1,4。
要求实现函数：
void array_iterate(int len, int input_array[], int m, int output_array[])
【输入】int len：输入数列的长度；int input_array[]：输入的初始数列 int m：初始计数值
【输出】int output_array[]：输出的数值出列顺序
【返回】无示例：
输入：int input_array[] = {3,1,2,4}，int len = 4，m=7
输出：output_array[] = {2,3,1,4}
 */
//vector<int> array_iterate(int n, vector<int>&input_array, int m)
//{
//    //初始计数值m
//    vector<int>exec_vec = input_array;
//    int total_count = m;
//    //随时变动
//    int exec_size = exec_vec.size();
//
//    //固定
//    int target_size = exec_size;
//    vector<int>result;
//
//    int index = 0;
//    while ((int)result.size()< target_size)
//    {
//        if (exec_size==1)
//        {
//            result.push_back(exec_vec[0]);
//            break;
//        }
//
//        while (index!=0) //调整index的位置到0
//        {
//            if (index==exec_size-1)
//            {
//                total_count--;
//                if (total_count == 0)
//                {
//                    index = 0;//下一轮开始的位置
//                    result.push_back(exec_vec[index]);
//                    total_count = exec_vec[index]; //下一轮的计数
//                    exec_vec.erase(exec_vec.begin() + index);
//                    exec_size = exec_vec.size();
//                	break;
//                }
//                index = 0;//下一轮开始的位置
//                break;
//                //if---
//            }
//            index++;
//            total_count--;
//            if (total_count == 0)
//            {
//                result.push_back(exec_vec[index]);
//                total_count = exec_vec[index];//下一轮的计数
//                exec_vec.erase(exec_vec.begin() + index);
//                exec_size = exec_vec.size();
//                break;
//            }
//        }
//
//        //先解决第一轮
//        if (total_count < exec_size)
//        {
//            int curr_pos = total_count - 1;
//            index = curr_pos;//下一轮开始的位置
//            result.push_back(exec_vec[curr_pos]);
//            total_count = exec_vec[curr_pos];//下一轮的计数
//            exec_vec.erase(exec_vec.begin() + curr_pos);
//            exec_size = exec_vec.size();
//        }
//        else if (total_count == exec_size)
//        {
//            //删掉最后一个，计数回到开头
//            index = 0;
//            result.push_back(exec_vec[exec_size - 1]);
//            total_count = exec_vec[exec_size - 1];//下一轮的计数
//            exec_vec.erase(exec_vec.begin() + exec_size - 1);
//            exec_size = exec_vec.size();
//        }
//        else
//        {
//            //取余
//            int curr_pos =  total_count % exec_size;
//            if (curr_pos==0)
//            {
//                curr_pos = exec_size - 1;
//            }
//            else
//            {
//                curr_pos -= 1;
//            }
//            index = curr_pos;//下一轮开始的位置
//            result.push_back(exec_vec[curr_pos]);
//            total_count = exec_vec[curr_pos];//下一轮的计数
//            exec_vec.erase(exec_vec.begin() + curr_pos);
//            exec_size = exec_vec.size();
//        }
//
//	    //while---
//    }
//    return result;
//
//	//
//}

vector<int> array_iterate(int n, vector<int>& input_array, int m)
{
    vector<int> exec_vec = input_array;
    vector<int> result;
    int index = 0;

    while (!exec_vec.empty()) {
        int size = exec_vec.size();
        index = (index + m - 1) % size;  // 计算当前要移除的位置
        m = exec_vec[index];             // 更新下一轮计数
        result.push_back(exec_vec[index]);
        exec_vec.erase(exec_vec.begin() + index);
    }

    return result;
}

/*
 “吃货”和“馋嘴”两人到披萨店点了一份铁盘（圆形）披萨，
 披萨切成了【奇数块】，且肉眼能分辨出大小。
由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：
从“吃货”开始，第一块披萨可以任意选取以外，其他都必须从缺口开始选。
他俩选披萨的思路不同。
“馋嘴”每次都会选最大块的披萨，而且“吃货"知道“馋嘴”的想法。
已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。

输入描述
第1行为一个正整数奇数N，表示披萨小块数量。3 <= N <= 500。
接下来的第2行到第N+1行(共N行)，每行为一个正整数，表示第ì块披萨的大小。1 <= i <= N。
披萨小块从某一块开始，按照一个方向依次顺序编号为1~N。每块披萨的大小范围为[1,21474836471]。
输出描述
“吃货”能分得的最大的披萨大小的总和

输入
5
8
2
10
5
7
输出
19
 */
class Solution01
{
public:
    Solution01(vector<long long>&origin_v)
    {
        int origin_size = origin_v.size();
        int ring_size = 2 * origin_size;
        vector<int>ring_v(ring_size);
        for (int i=0; i<ring_size; i++)
        {
            ring_v[i] = origin_v[i % origin_size];
        }

        vector<vector<long long>>dynamic_v(ring_size, vector<long long>(ring_size));

        //初始化，只有一块的情况
        for (int i=0; i<ring_size; i++)
        {
            dynamic_v[i][i] = ring_v[i];
        }

        //d只能取奇数块
        for (int d=3; d<=origin_size; d+=2)
        {
	        //start从0开始，取遍所有区间
            for (int start=0; start<ring_size-d; start++)
            {
                int end = start + d - 1;//最大取ring_size-1

                //start和end二选一
                //选了start start+1 end
                long long range_start_max = 0;
                if (ring_v[start+1]>ring_v[end])
                {
                    //start+2 end
                    range_start_max = dynamic_v[start + 2][end] + ring_v[start];
                }
                else
                {
                    //start+1 end-1
                    range_start_max = dynamic_v[start + 1][end - 1] + ring_v[start];
                }
                dynamic_v[start][end] = max(range_start_max, dynamic_v[start][end]);

                //选了end，start,end-1
                long long range_end_max = 0;
                if (ring_v[start]>ring_v[end-1])
                {
                    //start+1 end-1
                    range_end_max = dynamic_v[start + 1][end - 1] + ring_v[end];
                }
                else
                {
                    //start end-2
                    range_end_max = dynamic_v[start][end - 2] + ring_v[end];
                }
                dynamic_v[start][end] = max(range_end_max, dynamic_v[start][end]);

			//for---
            }
            //for---
        }


        //遍历所有区间取最大值
        long long result = 0;
        for (int i=0; i<origin_size; i++)
        {
            result = max(result, dynamic_v[i][i+origin_size-1]);
        }
        
        cout << result;
	    //Solution01
    }
};



/*
主管期望你实现一个基于字符串的N机制的减法。
需要对输入的两个字符串按照给定的N进制进行减法操作，输出正负符号和表示结果的字符串。
输入描述：
输入：
三个参数。
第一个参数是整数形式的进制N值，N值范围为大于等于2、小于等于35。
第二个参数为被减数字符串；
第三个参数为减数字符串
有效的字符包括0-9以及小写字母a-z，字符串有效字符个数最大为100个字符，另外还有结尾的0。

限制：
输入的被减数和减数，除了单独的0以外，不能是以0开头的字符串。
如果输入有异常或计算过程中有异常，此时应当输出-1表示错误。

输出描述：
输出：
2个。
其一为减法计算的结果，-1表示出错，0表示结果为整数，1表示结果为负数。
其二为表示结果的字符串。

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
2 11 1
输出
0 10
说明
按二进制计算 11 -1，计算正常，0表示符号为正数，结果为10
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
8 07 1
输出
-1
说明
按8进制，检查到减数不符合非0前导的要求，返回结果为-1，没有其他结果内容。
 */
class Solution02
{
public:
    void initCharMap(int N)
    {
        string total_char = "0123456789abcdefghijklmnopqrstuvwxyz";
        for (int i = 0; i < N; i++)
        {
            //int转成char
            char_map[i] = total_char[i];
        }

        for (auto&ch:total_char)
        {
            total_set.insert(ch);
        }

        //initCharMap
    }

    int getNum(char curr_ch)
    {
        if (isdigit(curr_ch))
        {
            return curr_ch - '0';
        }
        return curr_ch - 'a' + 10;
        //getNum
    }

    vector<string>getSort(string& str_a, string& str_b)
    {
        vector<string>result(2);

        if (str_a.size() > str_b.size())
        {
            result[0] = str_a;
            result[1] = str_b;
            return result;
        }
        if (str_b.size() > str_a.size())
        {
            result[0] = str_b;
            result[1] = str_a;
            return result;
        }
        //长度相等，逐位去比
        int size = str_a.size();
        for (int i = 0; i < size; i++)
        {
            if (str_a[i] > str_b[i])
            {
                result[0] = str_a;
                result[1] = str_b;
                break;
            }
            if (str_b[i] > str_a[i])
            {
                result[0] = str_b;
                result[1] = str_a;
                break;
            }
        }
        return result;
        //getSort
    }


    string substract(int N, string& big_str, string& small_str)
    {
        int big_size = big_str.size();
        int small_size = small_str.size();

        int big_i = big_size - 1;
        int small_i = small_size - 1;

        int carry = 0;
        string result;

        while (big_i >= 0)
        {
            int sum = carry;
            carry = 0;
            sum += getNum(big_str[big_i]);
            big_i--;

            if (small_i >= 0)
            {
                sum -= getNum(small_str[small_i]);
                small_i--;
            }
            if (sum < 0)
            {
                sum += N;
                carry = -1;
            }
            result += char_map.at(sum);
            //while---
        }
        reverse(result.begin(), result.end());

        //抹掉前导0
        while (result[0] == '0')
        {
            result = result.substr(1);
        }

        return result;
        //substract
    }

    bool checkStr(int N, string& str)
    {
        if (str == "0") return true;
        //减数不符合非0前导的要求
        if (str[0] == '0') return false;

        for (auto&ch:str)
        {
            if (total_set.count(ch) == 0) return false;
            int num = getNum(ch);
            if (num >= N) return false;
        }

        return true;
	    //check
    }
    bool checkVerify(int N, string& str_a, string& str_b)
    {
        //N值范围为大于等于2、小于等于35
        bool is_N = N >= 2 && N <= 35;
        if (!is_N) return false;

        return checkStr(N, str_a) && checkStr(N, str_b);
	    //check
    }

    Solution02(int N, string&str_a, string&str_b)
    {

        //1初始化char_map
        initCharMap(N);

        //2判断合规
        if (!checkVerify(N, str_a, str_b))
        {
            cout << -1;
            return;
        }

        //3比大小
        if (str_a==str_b)
        {
            cout << '0';
            return;
        }

        //第二个参数为被减数字符串；
        //第三个参数为减数字符串
        vector<string>sort_res = getSort(str_a, str_b);

        int sign = 0;
        //0表示结果为整数，1表示结果为负数
		if (sort_res[0]!=str_a)
		{
            sign = 1;
		}
        //其二为表示结果的字符串
        string res = substract(N, sort_res[0], sort_res[1]);

        cout << sign << ' ' << res;
	    //Solution02
    }
private:
    unordered_set<char>total_set;
    unordered_map<int, char>char_map;
};


int main()
{
	{
        int N;
        cin >> N;
        string str_a, str_b;
        cin >> str_a >> str_b;

        Solution02 solu(N, str_a, str_b);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;
        vector<long long>origin_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> origin_v[i];
        }
        Solution01 solu(origin_v);

        return 0;
	}
    // 处理输入
    //int len, m;
    //cin >> len >> m;
    //vector<int> nums;
    //for (int j = 0; j < len; j++) {
    //    int a;
    //    cin >> a;
    //    nums.push_back(a);
    //}
    //int input_array[] = {3,1,2,4}，int len = 4，m=7
    int len = 4, m = 7;
    vector<int>nums = { 3,1,2,4 };

    vector<int> res = array_iterate(len, nums, m);
    for (auto x : res) {
        cout << x << " ";
    }

    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
